package leetcode;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
/**
 * 1046.最后一块石头的重量
 * 有一堆石头，每块石头的重量都是正整数。
 * 每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为x 和y，且x <= y。那么粉碎的可能结果如下：
 * 如果x == y，那么两块石头都会被完全粉碎；
 * 如果x != y，那么重量为x的石头将会完全粉碎，而重量为y的石头新重量为y-x。
 * 最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0
 *
 * 输入：[2,7,4,1,8,1]
 * 输出：1
 */
public class Num_1046 {
    //优先级队列
    public int lastStoneWeight(int[] stones) {
        //基于最大堆的优先级队列
        Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        //入队操作
        for(int i = 0; i < stones.length; i++){
            queue.offer(stones[i]);
        }
        //操作的过程
        while (queue.size() > 1){
            int stone1 = queue.poll();
            int stone2 = queue.poll();
            if(stone1 == stone2){
                continue;
            }else{
                queue.offer(stone1 - stone2);
            }
        }
        //返回结果
        if(queue.isEmpty()){
            return 0;
        }else{
            return queue.peek();
        }
    }
}
